package xyf.p05.heap_trie;

import java.util.PriorityQueue;

/**
 * ClassName: P0295_DataMiddle
 * Description:
 * Author: xyf
 * Date: 9/23/22 9:03 PM
 * Version: 1.0
 **/
public class P0295_DataMiddle
{
    class MedianFinder
    {
        private PriorityQueue<Integer> minQueue = new PriorityQueue<>((a, b) -> (b - a));

        private PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> (a - b));

        public MedianFinder()
        {

        }

        public void addNum(int num)
        {
            if (minQueue.isEmpty() || num <= minQueue.peek())
            {
                minQueue.offer(num);
                if (minQueue.size() > maxQueue.size() + 1)
                {
                    Integer minNum = minQueue.poll();
                    maxQueue.offer(minNum);
                }
            }
            else
            {
                maxQueue.offer(num);
                if (maxQueue.size() > minQueue.size())
                {
                    Integer maxNum = maxQueue.poll();
                    minQueue.offer(maxNum);
                }
            }
        }

        public double findMedian()
        {
            if (minQueue.size() > maxQueue.size())
            {
                return minQueue.peek();
            }
            else
            {
                return (minQueue.peek() + maxQueue.peek()) / 2.0d;
            }
        }
    }
}